package algorithm;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author maguangqi
 * @version 1.0
 * https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
 * leetcode 第104题
 * 给定一个二叉树，找出其最大深度。
 * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 * <p>
 * 思路: 1. 使用BFS,第一级 3
 * 第二级 9, 20
 * 第三级 15,7
 * <p>
 * 思路: 2.使用DFS
 * @date 2020/7/7 20:32
 */
public class MaxDepth104 {
    /**
     * 使用BFS
     * 记住BFS 是层级访问,也就是最先最近入的元素先出来,符合队列的思想
     */
    public int maxDepth(TreeNode root) {

        //用一个队列保存元素
        if (root == null) {
            return 0;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int maxDepth = 0;
        while (!queue.isEmpty()) {
            maxDepth++;
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                //poll是从头取元素
                TreeNode curNode = queue.poll();
                //注意此处是取当前节点的left,不是root,或者说是队列里面元素的left
                if (curNode.left != null) {
                    queue.add(curNode.left);
                }
                if (curNode.right != null) {
                    queue.add(curNode.right);
                }
            }
        }
        return maxDepth;
    }

    /**
     * 解法二: 使用递归dfs
     * 找出终止条件：当前节点为空
     * 找出返回值：节点为空时说明高度为0，所以返回0；节点不为空时则分别求左右子树的高度的最大值，同时加1表示当前节点的高度，返回该数值
     * 某层的执行过程：在返回值部分基本已经描述清楚
     *
     */
    public int maxDepth2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        //加1表示当前节点的高度
        return Math.max(left,right)+1;
    }

    /**
     * 3
     * / \
     * 5   1
     * / \  / \
     * 6  2  0  8
     * / \
     * 7   4
     */
    public static void main(String[] args) {
        MaxDepth104 maxDepth104 = new MaxDepth104();
        TreeNode treeNode = new TreeNode(3);
        TreeNode treeNode1 = new TreeNode(5);
        TreeNode treeNode2 = new TreeNode(1);
        TreeNode treeNode3 = new TreeNode(6);
        TreeNode treeNode4 = new TreeNode(2);
        TreeNode treeNode5 = new TreeNode(0);
        TreeNode treeNode6 = new TreeNode(8);
        TreeNode treeNode7 = new TreeNode(7);
        TreeNode treeNode8 = new TreeNode(4);
        treeNode4.left = treeNode7;
        treeNode4.right = treeNode8;
        treeNode1.left = treeNode3;
        treeNode1.right = treeNode4;
        treeNode2.left = treeNode5;
        treeNode2.right = treeNode6;
        treeNode.left = treeNode1;
        treeNode.right = treeNode2;
        System.out.println(maxDepth104.maxDepth(treeNode));
    }
}
